
package org.spp.batchedAccess;

import java.util.List;
import java.util.ArrayList;

import org.spp.voronoi.Centroid;
import org.spp.voronoi.VoronoiDiagram;
import org.spp.voronoi.Vertex;

/**
 *
 * @author Ilio Catallo, Eleonora Ciceri
 * @version 1.0
 * 
 * Description: the class implements the SPP algorithm
 * 
 * Date: Jul 10, 2011
 */
public class SPP {
    
    // Attributes
    private Double alpha;
    private Double initialM;
    private String budgetType;

    private BatchedAccess batchedAccess;
    
    private int[] sumDepths;
    private int[] sDepths;


   /**
     * Constructor for the class SPP
     * @param alpha 
     * @param initialM
     * @param budgetType 
     * @param epsilon 
     */
    public SPP(double alpha, double initialM, String budgetType, double epsilon) {
        this.alpha = alpha;
        this.initialM = initialM;
        this.budgetType = budgetType;
        
        this.batchedAccess = new BatchedAccess(epsilon);
    }
    
    /**
     * Method that returns the score depths (number of objects that are retrieved
     * using score based access in each iteration of SPP)
     * @return sDepths
     */    
    public int[] getSDepths() {
        return sDepths;
    }
    
    /**
     * Method that returns the sum of the depths (the total number of retrieved 
     * objects, using both the score based access and the distance based access)
     * @return sumDepths
     */
    public int[] getSumDepths() {
        return sumDepths;
    }
    
    /**
     * Method that returns the budget used in the current iteration of SPP
     * @param k
     * @return M
     */    
    private double computeNewBudget(int k) {
        // Variables
        double M;
        
        if (budgetType.compareTo("linear") == 0)
            M = initialM;
        else {
            double beta = (double)(90.0 / (Math.pow(10, alpha) - 1));
            M = (Double)(beta * Math.pow(k, alpha) - beta * Math.pow(k - 1, alpha));
        }
        
        return M;
    }
    
    /**
     * Method that applies the SPP algorithm in order to retrieve K objects
     * @param K
     * @param invoker
     * @param lambda
     * @param N
     * @return centroids
     */
    public List<Centroid> run(int K, Invoker invoker, double lambda, int N) {
        // Variables
        List<Centroid> centroids = new ArrayList<Centroid>();
        List<Centroid> seenObjects = new ArrayList<Centroid>(); 
        int Sdepth = 1;
        int Vdepth = 0;
        double Smax = 1; 
        double a = ((double)1) / N;        
        double rho = N;  
        
        // Retrieve the object with the higher score
        Centroid x = invoker.pullObjectByScore(Sdepth-1);
        
        sumDepths = new int[K];
        sDepths = new int[K];
        sumDepths[0] = 1;
        sDepths[0] = 1;
        
        double M = computeNewBudget(2);
        
        // Collection of the top-K objects
        for (int k = 2; k <= K; k++) {
            centroids.add(x);
            
            VoronoiDiagram voronoiDiagram = new VoronoiDiagram(centroids);
            batchedAccess.computeRadiiAndBudget(voronoiDiagram.getVertexes(), M, "distScore", lambda, Smax, a, Sdepth, rho);
            
            //Pull the objects by score
            double Ms = batchedAccess.getScoreBudget();
            
            for (int i = 0; i < Math.floor(Ms); i++) {
                
                Centroid newObjectByScore = invoker.pullObjectByScore(Sdepth);
                
                seenObjects.add(newObjectByScore);                
                Sdepth++;
            }
            sDepths[k-1] = sDepths[k-2] + (int)Math.floor(Ms); 
            
            // Pull the objects by distance
            for (int i = 0; i < batchedAccess.getNumRadii(); i++) {
                Vertex vertex = batchedAccess.getVertex(i);
                double radius = batchedAccess.getRadius(i);
                
                List<Centroid> seenObjectsByDistance = invoker.pullObjectByDistance(vertex, radius);
                for (int j = 0; j < seenObjectsByDistance.size(); j++)
                    seenObjects.add(seenObjectsByDistance.get(j));
                
                Vdepth += seenObjectsByDistance.size();
            }
            
            // Update the seen objects counter
            sumDepths[k-1] = sumDepths[k-2] + Vdepth + (int)Math.floor(Ms);
            
            // Compute the diversity weighted score for each object
            invoker.computeDivScores(lambda, centroids);            
            
            // Choose a new object
            x = findCurrentBest(centroids, seenObjects, invoker);
            
            M = computeNewBudget(k+1);            
            Vdepth = 0;
        }
        
        centroids.add(x);
        return centroids;
    }
    
    /**
     * Method that finds the best objects between the objects that were visited
     * during the current iteration
     * @param centroids
     * @param seenObjects 
     * @param invoker 
     * @return centroid
     */    
    private Centroid findCurrentBest(List<Centroid> centroids, List<Centroid> seenObjects, Invoker invoker) {  
        // Variables
        double maxScore = Double.NEGATIVE_INFINITY;
        Centroid bestObject = null;

        List<Centroid> notSelectedObjects = new ArrayList<Centroid>();
        notSelectedObjects.addAll(seenObjects);
        notSelectedObjects.removeAll(centroids);
        
        // Select the best object
        for (int i = 0; i < notSelectedObjects.size(); i++)
            if (maxScore < (notSelectedObjects.get(i)).getDivScore()){
                maxScore = (notSelectedObjects.get(i)).getDivScore();
                bestObject = notSelectedObjects.get(i);
            }                
        
        return bestObject;
    }
    
    /**
     * Method that prints the found results for SPP and MMR
     * @param SPPresults
     * @param FOSpp 
     * @param sumDepths 
     * @param sDepths 
     * @param MMRresults 
     * @param FOMmr
     */    
    private void printResults(List<Centroid> SPPresults, double FOSpp, int[] sumDepths, int[] sDepths, List<Centroid> MMRresults, double FOMmr) {
        System.out.println("Risultati MMR: ");
        for (int i = 0; i < MMRresults.size(); i++)
            System.out.println(" - " + MMRresults.get(i).getId());        
        
        System.out.println("FO MMR: " + FOMmr);
        System.out.println("Risultati SPP: ");
        for (int i = 0; i < SPPresults.size(); i++)
            System.out.println(" - " + SPPresults.get(i).getId());
        
        System.out.println("FO SPP: " + FOSpp);
        
        String sumDepthsString = new String();
        for (int i = 0; i < sumDepths.length; i++)
            sumDepthsString = sumDepthsString + " - " + sumDepths[i];
        System.out.println("sumDepths: " + sumDepthsString);

        String sDepthsString = new String();
        for (int i = 0; i < sDepths.length; i++)
            sDepthsString = sDepthsString + " - " + sDepths[i];
        System.out.println("sDepths: " + sDepthsString);
    }
    
    
    /**
     * Main
     */
    public static void main(String[] args) {
        // Variables
        int N = 10000;
        double lambda = 0.75;
        double epsilon = 0.00000001;
        int K = 10;
        double alpha = 0.5;
        double initialM = 10.0;
        String budgetType = "linear";
        int dimension = 2;
        
        Invoker invoker = invoker = new Invoker(N, 1, dimension);
        
        SPP Spp = new SPP(alpha, initialM, budgetType, epsilon);       
        List<Centroid> SPPresults = Spp.run(K, invoker, lambda, N);
        double FOSpp = invoker.computeObjectiveFunction(SPPresults, lambda);
        int[] sumDepths = Spp.getSumDepths();
        int[] sDepths = Spp.getSDepths();
        
        MMR Mmr = new MMR();
        List<Centroid> MMRresults = Mmr.run(K, invoker, lambda);
        double FOMmr = invoker.computeObjectiveFunction(MMRresults, lambda);
        
        Spp.printResults(SPPresults, FOSpp, sumDepths, sDepths, MMRresults, FOMmr);        
    }
    
}
